package com.example.algorithm.huawei_rongyao_29;
import java.util.Arrays;
import java.util.Scanner;

// 数组中值出现了一次的数字
// 难度：???
/**
 * 数组中值出现了一次的数字
 * 给定一个数字arr，其中只有有两个数字出现了奇数次，其它数字都出现了偶数次，按照从小到大顺序输出这两个数。
 * 输入描述:
 * 输入包含两行，第一行一个整数n(1<=n<=10的5次方，代表数组arr的长度，第二行n个整数，代表数组arr,arr[i]为32位整数。
 * 输出描述:
 * 输出出现奇数次的两个数，按照从小到大的顺序。
 * 备注:
 * 时间复杂度0（n）,额外空间复杂度o(1)
 *
 * 示例1
 * 输入
 * 4
 * 1 1 2 3
 * 输出
 * 2 3
 *
 * 示例2
 * 输入
 * 6
 * 11 22 11 23 23 45
 * 输出
 * 22 45
 *
 * 一个数字与自己异或结果为0，即 a ^ a = 0。
 * 一个数字与0异或结果为它自己，即 a ^ 0 = a。
 * 异或运算满足交换律和结合律。
 *
 * 具体步骤
 * 对数组中的所有数字进行一次整体异或，结果为两个出现奇数次的数字的异或结果 xor_result。
 * 通过 xor_result，找出这两个数字在某一位上的不同（任何一位上不同都可以），我们此程序实际用 xor_result & -xor_result 找到最右边的不同位。
 * 根据这一位将数组分成两组，每组分别只包含一个奇数次的数字，对每组进行异或运算即可得到这两个数字。(大致意思就是，转换为了数组中有单个奇数次元素的问题了。这个就非常好处理了。)
 * 将这两个数字按从小到大的顺序输出。
 *
 * 以下程序经过实际测试，结果正确。
 * */
public class Q25_FindOddOccurringNumbers {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 千万注意哦，nextInt与nextLine不能在一个方法内混用，否则会报错
        int n = Integer.parseInt(scanner.nextLine());
        int[] arr = Utils.scannerAndTransIntoInt(scanner.nextLine());
        int[] result = findOddOccurringNumbers(arr);
        //排序是因为输出result要求自然升序
        Arrays.sort(result);
        System.out.println(result[0] + " " + result[1]);
    }

    public static int[] findOddOccurringNumbers(int[] arr) {
        int xor_result = 0;
        for (int num : arr) {
            // 其实就是拿xor_result = 0这个初始值和每一个num异或。最后累积下来的xor_result就是两个目标数的异或
            xor_result = xor_result^num;
        }

        // Find the rightmost set bit (bit difference between the two odd occurring numbers)
        // 这段代码有些操过知识范围了。在本代码下面的备注有专门讲解这句代码的含义。
        int rightmost_set_bit = xor_result & -xor_result;

        // num1、num2分别是用来做两组异或的初始值。
        // 由于此时两组异或分别已经是1个落单数字，说以，最终完全异或完之后，num1、num2就是我们最终求的原始数组中的两个落单值。
        int num1 = 0, num2 = 0;
        for (int num : arr) {
            if ((num & rightmost_set_bit) == 0) {
                num1 ^= num;
            } else {
                num2 ^= num;
            }
        }

        return new int[] { num1, num2 };
    }
}

// 备注：int rightmost_set_bit = xor_result & -xor_result; 这句代码是什么意思
// 这句代码 `int rightmost_set_bit = xor_result & -xor_result;` 用于找到整数 `xor_result` 中最右边的置位（即最右边的1位）。这是一个常见的位运算技巧。我们来详细解释一下其工作原理：
//
//### 解释
//
//1. **`xor_result`**:
//   - 这是一个整数，假设它的二进制形式为 `...1000...0`。
//
//2. **`-xor_result`**:
//   - 这是 `xor_result` 的补码表示。计算一个数的负数在二进制中可以通过以下步骤完成：
//     - 取反（即将每一位取反，0变1，1变0）。
//     - 对取反后的结果加1。
//
//    举个例子，假设 `xor_result` 为 12，其二进制表示为 `00001100`。取反后为 `11110011`，再加1得到 `11110100`。所以 `-xor_result` 为 `11110100`。
//
//3. **`xor_result & -xor_result`**:
//   - 这是与运算 `&`。该运算仅在两个操作数的相应位都为1时结果才为1。
//   - 由于负数的补码表示只保留了原数最右边的1位及其后的所有0，并将前面的位取反，因此 `xor_result` 和 `-xor_result` 做与运算会保留最右边的1位。
//
//### 举例
//
//假设 `xor_result` 为 12，其二进制表示为 `00001100`。
//
//1. `xor_result` = `00001100`
//2. `-xor_result` = `11110100`
//
//做与运算：
//```
//00001100
//&
//11110100
//---------
//00000100
//```
//
//结果是 `00000100`，即 `4`，表示最右边的置位是第三位（从右边开始算起）。
//
//### 总结
//
//- 这句代码用于找到整数 `xor_result` 中最右边的1位。
//- 这是通过利用补码表示和与运算实现的。
//- 结果是一个仅有最右边置位为1，其余位为0的数。
//
//### 代码应用场景
//
//这个操作在很多算法中都有应用，例如：
//- 快速找到一个整数中最右边的1位位置。
//- 在位图、位操作相关的算法中，例如位图法进行集合运算。
//- 在某些特定的数论算法中，例如快速计算最大公约数。
//
//这段代码简洁高效，在处理位操作问题时非常有用。

